package arithmetic.LeetCode;

import org.junit.jupiter.api.Test;

/**
 * 53. 最大子数组和
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组 是数组中的一个连续部分。
 *
 * <a href="https://leetcode.cn/problems/maximum-subarray/">...</a>
 * @author jiangfeng on 2023/4/9
 */
public class MaxSubarray {
    @Test
    public void test(){
        System.out.println(maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
        System.out.println(maxSubArray1(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }

    public int maxSubArray(int[] nums) {
        // 起始index, 末尾n
        // 状态转换方程: pb[n] = Max{pb[n-1] + nums[n],nums[n]} ,表示以pb[n]为结尾的子数组最大值.
        // 需要注意的是,这个状态方程没有记录历史最大的连续值.所以需要辅助数组来帮忙计算
        int[] pb = new int[nums.length];
        int currMax = nums[0];
        pb[0]=nums[0];

        for(int i =1;i<nums.length;i++){
            pb[i] = Math.max(pb[i-1]+nums[i],nums[i]);
            currMax = Math.max(currMax,pb[i]);
        }
        return currMax;
    }


    // 变量优化版
    public int maxSubArray1(int[] nums) {
        int pre = nums[0], currMax = nums[0];
        for(int i =1;i<nums.length;i++){
            pre = Math.max(pre+nums[i],nums[i]);
            currMax = Math.max(currMax,pre);
        }
        return currMax;
    }
}
